{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Get the Maximum Score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #two-pointers #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #双指针 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大得分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有两个 <strong>有序</strong>&nbsp;且数组内元素互不相同的数组&nbsp;<code>nums1</code> 和&nbsp;<code>nums2</code>&nbsp;。</p>\n",
    "\n",
    "<p>一条&nbsp;<strong>合法路径</strong>&nbsp;定义如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择数组 <code>nums1</code> 或者 <code>nums2</code> 开始遍历（从下标 0 处开始）。</li>\n",
    "\t<li>从左到右遍历当前数组。</li>\n",
    "\t<li>如果你遇到了 <code>nums1</code>&nbsp;和 <code>nums2</code>&nbsp;中都存在的值，那么你可以切换路径到另一个数组对应数字处继续遍历（但在合法路径中重复数字只会被统计一次）。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>得分</strong> 定义为合法路径中不同数字的和。</p>\n",
    "\n",
    "<p>请你返回 <em>所有可能 <strong>合法路径</strong> 中的最大得分。</em>由于答案可能很大，请你将它对 10^9 + 7 取余后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/08/02/sample_1_1893.png\" style=\"height: 163px; width: 538px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]\n",
    "<strong>输出：</strong>30\n",
    "<strong>解释：</strong>合法路径包括：\n",
    "[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],（从 nums1 开始遍历）\n",
    "[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]  （从 nums2 开始遍历）\n",
    "最大得分为上图中的绿色路径 <strong>[2,4,6,8,10]</strong>&nbsp;。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [1,3,5,7,9], nums2 = [3,5,100]\n",
    "<strong>输出：</strong>109\n",
    "<strong>解释：</strong>最大得分由路径 <strong>[1,3,5,100]</strong> 得到。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]\n",
    "<strong>输出：</strong>40\n",
    "<strong>解释：</strong>nums1 和 nums2 之间无相同数字。\n",
    "最大得分由路径[6,7,8,9,10]得到。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums1.length, nums2.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums1[i], nums2[i] &lt;= 10<sup>7</sup></code></li>\n",
    "\t<li><code>nums1</code> 和&nbsp;<code>nums2</code>&nbsp;都是严格递增的数组。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [get-the-maximum-score](https://leetcode.cn/problems/get-the-maximum-score/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [get-the-maximum-score](https://leetcode.cn/problems/get-the-maximum-score/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,4,5,8,10]\\n[4,6,8,9]', '[1,3,5,7,9]\\n[3,5,100]', '[1,2,3,4,5]\\n[6,7,8,9,10]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # 两个数组相等的值，将两个数组分成了相同的段数，只需要每一段都取较大的值就行了\n",
    "        MOD = 10**9+7\n",
    "        pos1,pos2 = 0,0\n",
    "        len1,len2 = len(nums1),len(nums2)\n",
    "        total = 0\n",
    "        temp1,temp2 = 0,0\n",
    "        while pos1<len1 and pos2<len2:\n",
    "            while (pos1<len1 and pos2<len2) and not nums1[pos1]==nums2[pos2]:\n",
    "                if nums1[pos1] < nums2[pos2]:\n",
    "                    temp1 += nums1[pos1]\n",
    "                    pos1+=1\n",
    "                else:\n",
    "                    temp2 += nums2[pos2]\n",
    "                    pos2+=1\n",
    "\n",
    "            if pos1<len1 and pos2<len2:\n",
    "                temp1+=nums1[pos1]\n",
    "                temp2+=nums2[pos2]\n",
    "                total = (total + max(temp1, temp2))%MOD\n",
    "                temp1,temp2 = 0,0\n",
    "                pos1,pos2 = pos1+1,pos2+1           \n",
    "            pass\n",
    "\n",
    "        while pos1<len1:\n",
    "            temp1+=nums1[pos1]\n",
    "            pos1+=1\n",
    "        while pos2<len2:\n",
    "            temp2+=nums2[pos2]\n",
    "            pos2+=1\n",
    "        total += max(temp1,temp2)\n",
    "        return total%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        MOD = 10**9+7\n",
    "        pos1,pos2 = 0,0\n",
    "        len1,len2 = len(nums1),len(nums2)\n",
    "        total = 0\n",
    "        temp1,temp2 = 0,0\n",
    "        while pos1<len1 and pos2<len2:\n",
    "            while (pos1<len1 and pos2<len2) and not nums1[pos1]==nums2[pos2]:\n",
    "                if nums1[pos1] < nums2[pos2]:\n",
    "                    temp1 += nums1[pos1]\n",
    "                    pos1+=1\n",
    "                else:\n",
    "                    temp2 += nums2[pos2]\n",
    "                    pos2+=1\n",
    "\n",
    "            if pos1<len1 and pos2<len2:\n",
    "                temp1+=nums1[pos1]\n",
    "                temp2+=nums2[pos2]\n",
    "                total = (total + max(temp1, temp2))%MOD\n",
    "                temp1,temp2 = 0,0\n",
    "                pos1,pos2 = pos1+1,pos2+1           \n",
    "            pass\n",
    "\n",
    "        while pos1<len1:\n",
    "            temp1+=nums1[pos1]\n",
    "            pos1+=1\n",
    "        while pos2<len2:\n",
    "            temp2+=nums2[pos2]\n",
    "            pos2+=1\n",
    "        total += max(temp1,temp2)\n",
    "        return total%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "\n",
    "        sum1 = 0 # 累积走nums1的和\n",
    "        sum2 = 0 # 累积走nums2的和\n",
    "        INF = int(math.pow(10, 9) + 7)\n",
    "\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        i, j = 0, 0\n",
    "        while i<m and j <n:\n",
    "            if nums1[i] < nums2[j]:\n",
    "                sum1 = sum1 + nums1[i]\n",
    "                i += 1\n",
    "            elif nums1[i] > nums2[j]:\n",
    "                sum2 = sum2 + nums2[j]\n",
    "                j += 1\n",
    "            else: \n",
    "                # 遇到岔路口, 两者都更新为大值 （相当于大的路径把小的路径覆盖了）    \n",
    "                sum1 = sum2 = (max(sum1,sum2) + nums1[i]) % INF\n",
    "                i += 1\n",
    "                j += 1\n",
    "\n",
    "        # 加上剩余的数字\n",
    "        sum1, sum2 = sum1 + sum(nums1[i:]), sum2 + sum(nums2[j:])\n",
    "        return max(sum1, sum2) % INF\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        i, j = 0, 0\n",
    "        a, b = 0, 0\n",
    "        aa,bb = 0,0\n",
    "        MOD = 10**9+7\n",
    "        while i < m and j < n:\n",
    "            if nums1[i] == nums2[j]:\n",
    "                a, b = nums1[i] + a, nums2[j] + b\n",
    "                t,tt =0,0\n",
    "                if aa>bb or (aa==bb and a>b):\n",
    "                    b = a\n",
    "                    bb = aa\n",
    "                else:\n",
    "                    a = b\n",
    "                    aa = bb\n",
    "\n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif nums1[i] < nums2[j]:\n",
    "                a = a + nums1[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                b = b + nums2[j]\n",
    "                j += 1\n",
    "            aa+=a//MOD\n",
    "            a%=MOD\n",
    "            bb+=b//MOD\n",
    "            b%=MOD\n",
    "        while i < m:\n",
    "            a += nums1[i]\n",
    "            i += 1\n",
    "            aa+=a//MOD\n",
    "            a%=MOD\n",
    "        while j < n:\n",
    "            b += nums2[j]\n",
    "            j += 1\n",
    "            bb+=b//MOD\n",
    "            b%=MOD\n",
    "        print(a,aa,b,bb)\n",
    "        return a if aa>bb or (aa==bb and a>b) else b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        sum1 = sum2 = 0\n",
    "        max1 = 0\n",
    "        i = j = 0\n",
    "        mod = 10**9+7\n",
    "        while i< len(nums1) and j <len(nums2):\n",
    "            if nums1[i]<nums2[j]:\n",
    "                sum1+=nums1[i]\n",
    "                i+=1\n",
    "            elif nums2[j]<nums1[i]:\n",
    "                sum2+=nums2[j]\n",
    "                j+=1\n",
    "            else:\n",
    "                sum1 = sum2 = max(sum1,sum2) + nums1[i]\n",
    "                i+=1\n",
    "                j+=1\n",
    "        \n",
    "        return max(sum1 + sum(nums1[i:]), sum2 + sum(nums2[j:]))%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        sum1,sum2=0,0\n",
    "        mod=10**9+7\n",
    "        i=j=0\n",
    "        while i<len(nums1) and j <len(nums2):\n",
    "            if nums1[i]<nums2[j]:\n",
    "                sum1+=nums1[i]\n",
    "                i+=1\n",
    "            elif nums1[i]>nums2[j]:\n",
    "                sum2+=nums2[j]\n",
    "                j+=1\n",
    "            else:\n",
    "                # 这边遇到相同值，说明可以切换线路。那么就相当于下面一个线路，可以从nums1和nums2过来都行，要求最大值那么直接取原来最大值即可\n",
    "                sum1=sum2=max(sum1,sum2)+nums1[i]\n",
    "                i+=1\n",
    "                j+=1    \n",
    "        sum1,sum2=sum1+sum(nums1[i:]),sum2+sum(nums2[j:])\n",
    "        return max(sum1,sum2)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n=len(nums1)\n",
    "        m=len(nums2)\n",
    "        i=0\n",
    "        j=0\n",
    "        sum1=0\n",
    "        sum2=0\n",
    "        while i<n and j<m:\n",
    "            if nums1[i]<nums2[j]:\n",
    "                sum1+=nums1[i]\n",
    "                i+=1\n",
    "            elif nums1[i]>nums2[j]:\n",
    "                sum2+=nums2[j]\n",
    "                j+=1\n",
    "            else:\n",
    "                sum1=sum2=max(sum1,sum2)+nums1[i]\n",
    "                i+=1\n",
    "                j+=1\n",
    "        sum1,sum2=sum1+sum(nums1[i:]),sum2+sum(nums2[j:])\n",
    "        return max(sum1,sum2)%(10**9+7)\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # dic={}\n",
    "        # node=[]\n",
    "        # for i,x in enumerate(nums1):\n",
    "        #     dic[x]=i\n",
    "        # for j,y in enumerate(nums2):\n",
    "        #     if y in dic:\n",
    "        #         node.append((dic[y],j,y))\n",
    "        # if not node:\n",
    "        #     return max(sum(nums1),sum(nums2))\n",
    "        \n",
    "        # s1=[nums1[0]]\n",
    "        # s2=[nums2[0]]\n",
    "        # for i in range(1,n):\n",
    "        #     s1.append(nums1[i]+s1[-1])\n",
    "        # for i in range(1,m):\n",
    "        #     s2.append(nums2[i]+s2[-1])\n",
    "\n",
    "        # ans=0\n",
    "        # b_i=-1\n",
    "        # b_j=-1\n",
    "        # for o in node:\n",
    "        #     i=o[0]\n",
    "        #     j=o[1]\n",
    "        #     if b_i<0 or b_j<0:\n",
    "        #         ans+=max(s1[i],s2[j])\n",
    "        #     else:\n",
    "        #         ans+=max(s1[i]-s1[b_i],s2[j]-s2[b_j])\n",
    "        #     b_i=i\n",
    "        #     b_j=j\n",
    "        # if b_i<n or b_j<m:\n",
    "        #     ans+=max(s1[-1]-s1[b_i],s2[-1]-s2[b_j])\n",
    "        # return ans%(10**9+7)           \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    https://leetcode.cn/problems/get-the-maximum-score/solutions/357534/cshuang-zhi-zhen-fen-duan-tong-ji-zui-da-he-xiang-/\n",
    "    这个题解中的图一目了然。不管从哪个数组出发，遇到相交点的时候两条路径一定会重合，那么没有相交部分的两条路径就选一条路径和最大的，并将这些分段最大\n",
    "    值的路径和加起来，就是答案了\n",
    "    实现方面，用双指针表示当前两个数组走到的下标，那条路小就走那条路，这样才能在逐渐增大的过程中遇到较大的那条路中的相同点，\n",
    "    如果发现相同点，将两条路都同时更新为分段和最大的那条路径和，由于存在最后一段分开走的可能，所以最后还是需要再比较一下两条\n",
    "    路径和哪条最大的\n",
    "    '''\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        v1, v2 = 0, 0\n",
    "        i, j = 0, 0\n",
    "\n",
    "        while i < m and j < n:\n",
    "            if nums1[i] < nums2[j]:\n",
    "                v1 += nums1[i]\n",
    "                i += 1\n",
    "            elif nums1[i] > nums2[j]:\n",
    "                v2 += nums2[j]\n",
    "                j += 1\n",
    "            else:\n",
    "                v1 = v2 = max(v1, v2) + nums1[i]\n",
    "                i += 1\n",
    "                j += 1\n",
    "        \n",
    "        while i < m:\n",
    "            v1 += nums1[i]\n",
    "            i += 1\n",
    "        while j < n:\n",
    "            v2 += nums2[j]\n",
    "            j += 1\n",
    "        \n",
    "        return max(v1, v2) % mod\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        sum1,sum2,i,j,INF=0,0,0,0,int(math.pow(10,9)+7)\n",
    "        while i<len(nums1) and j<len(nums2):\n",
    "            if nums1[i]<nums2[j]:\n",
    "                sum1 +=nums1[i]\n",
    "                i +=1\n",
    "            elif nums2[j]<nums1[i]:\n",
    "                sum2 +=nums2[j]\n",
    "                j +=1\n",
    "            else:\n",
    "                sum1=sum2=(max(sum1,sum2)+nums1[i]) % INF\n",
    "                i +=1\n",
    "                j +=1\n",
    "        sum1,sum2=sum1+sum(nums1[i:]),sum2+sum(nums2[j:])\n",
    "        return max(sum1,sum2)%INF\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        i, j = 0, 0\n",
    "        a, b = 0, 0\n",
    "        aa,bb = 0,0\n",
    "        MOD = 10**9+7\n",
    "        while i < m and j < n:\n",
    "            if nums1[i] == nums2[j]:\n",
    "                a, b = nums1[i] + a, nums2[j] + b\n",
    "                t,tt =0,0\n",
    "                aa+=a//MOD\n",
    "                a%=MOD\n",
    "                bb+=b//MOD\n",
    "                b%=MOD\n",
    "                if aa>bb or (aa==bb and a>b):\n",
    "                    b = a\n",
    "                    bb = aa\n",
    "                else:\n",
    "                    a = b\n",
    "                    aa = bb\n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif nums1[i] < nums2[j]:\n",
    "\n",
    "                a = a + nums1[i]\n",
    "                i += 1\n",
    "                aa+=a//MOD\n",
    "                a%=MOD\n",
    "            else:\n",
    "                b = b + nums2[j]\n",
    "                j += 1\n",
    "                bb+=b//MOD\n",
    "                b%=MOD\n",
    "            # aa+=a//MOD\n",
    "            # a%=MOD\n",
    "            # bb+=b//MOD\n",
    "            # b%=MOD\n",
    "        while i < m:\n",
    "            a += nums1[i]\n",
    "            i += 1\n",
    "            aa+=a//MOD\n",
    "            a%=MOD\n",
    "        while j < n:\n",
    "            b += nums2[j]\n",
    "            j += 1\n",
    "            bb+=b//MOD\n",
    "            b%=MOD\n",
    "        print(a,aa,b,bb)\n",
    "        return a if aa>bb or (aa==bb and a>b) else b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        i, j = 0, 0\n",
    "        ans = 0\n",
    "        a, b = 0, 0\n",
    "        while i < m and j < n:\n",
    "            if nums1[i] == nums2[j]:\n",
    "                a, b = nums1[i] + a, nums2[j] + b\n",
    "                t = max(a, b)\n",
    "                a, b = t, t\n",
    "                i += 1\n",
    "                j += 1\n",
    "                ans = max(ans, t)\n",
    "            elif nums1[i] < nums2[j]:\n",
    "                a = a + nums1[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                b = b + nums2[j]\n",
    "                j += 1\n",
    "        while i < m:\n",
    "            a += nums1[i]\n",
    "            i += 1\n",
    "        while j < n:\n",
    "            b += nums2[j]\n",
    "            j += 1\n",
    "        return max(a, b)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        sum1, sum2, i, j, INF = 0, 0, 0, 0, int(math.pow(10, 9) + 7)\n",
    "        while i < len(nums1) and j < len(nums2):\n",
    "            # 小的一方先走\n",
    "            if nums1[i] < nums2[j]:\n",
    "                sum1 += nums1[i]\n",
    "                i += 1\n",
    "            elif nums2[j] < nums1[i]:\n",
    "                sum2 += nums2[j]\n",
    "                j += 1\n",
    "            else:\n",
    "                # 遇到岔口，更新两个sum为最大值，同时取余\n",
    "                sum1 = sum2 = (max(sum1, sum2) + nums1[i]) % INF\n",
    "                i += 1\n",
    "                j += 1\n",
    "\n",
    "        # 加上数组中剩余的数字\n",
    "        sum1, sum2 = sum1 + sum(nums1[i:]), sum2 + sum(nums2[j:])\n",
    "\n",
    "        # 返回较大者取余的结果\n",
    "        return max(sum1, sum2) % INF\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        i = j = pre1 = pre2 = 0\n",
    "        while i < m and j < n:\n",
    "            if nums1[i] < nums2[j]:\n",
    "                pre1 += nums1[i]\n",
    "                i += 1\n",
    "            elif nums1[i] > nums2[j]:\n",
    "                pre2 += nums2[j]\n",
    "                j += 1\n",
    "            else:\n",
    "                pre1 += nums1[i]\n",
    "                pre2 += nums2[j]\n",
    "                pre1 = pre2 = pre1 if pre1 > pre2 else pre2\n",
    "                i += 1\n",
    "                j += 1\n",
    "        pre1 += sum(nums1[i:])\n",
    "        pre2 += sum(nums2[j:])\n",
    "        return max(pre1, pre2) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self,nums1:List[int],nums2:List[int])->int:\n",
    "        sum1,sum2,i,j,INF=0,0,0,0,int(math.pow(10,9)+7)\n",
    "        while i<len(nums1) and j<len(nums2):\n",
    "            if nums1[i]<nums2[j]:\n",
    "                sum1 +=nums1[i]\n",
    "                i +=1\n",
    "            elif nums2[j]<nums1[i]:\n",
    "                sum2 +=nums2[j]\n",
    "                j +=1\n",
    "            else:\n",
    "                sum1=sum2=(max(sum1,sum2)+nums1[i])\n",
    "                i +=1\n",
    "                j +=1\n",
    "        sum1,sum2=sum1+sum(nums1[i:]),sum2+sum(nums2[j:])\n",
    "        return max(sum1,sum2)%INF\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self,nums1:List[int],nums2:List[int])->int:\n",
    "        sum1,sum2,i,j,INF=0,0,0,0,int(math.pow(10,9)+7)\n",
    "        while i<len(nums1) and j<len(nums2):\n",
    "            if nums1[i]<nums2[j]:\n",
    "                sum1 +=nums1[i]\n",
    "                i +=1\n",
    "            elif nums2[j]<nums1[i]:\n",
    "                sum2 +=nums2[j]\n",
    "                j +=1\n",
    "            else:\n",
    "                sum1=sum2=(max(sum1,sum2)+nums1[i])%INF\n",
    "                i +=1\n",
    "                j +=1\n",
    "        sum1,sum2=sum1+sum(nums1[i:]),sum2+sum(nums2[j:])\n",
    "        return max(sum1,sum2)%INF\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self,nums1:List[int],nums2:List[int])->int:\n",
    "        sum1,sum2,i,j,INF=0,0,0,0,int(math.pow(10,9)+7)\n",
    "        while i<len(nums1) and j<len(nums2):\n",
    "            if nums1[i]<nums2[j]:\n",
    "                sum1 +=nums1[i]\n",
    "                i +=1\n",
    "            elif nums2[j]<nums1[i]:\n",
    "                sum2 +=nums2[j]\n",
    "                j +=1\n",
    "            else:\n",
    "                sum1=sum2=(max(sum1,sum2)+nums1[i])\n",
    "                i +=1\n",
    "                j +=1\n",
    "        sum1,sum2=sum1+sum(nums1[i:]),sum2+sum(nums2[j:])\n",
    "        return max(sum1,sum2)%INF\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m=len(nums1)\n",
    "        n=len(nums2)\n",
    "        i=0\n",
    "        j=0\n",
    "        sum1=0\n",
    "        sum2=0\n",
    "        mod=10**9+7\n",
    "        while i<m and j<n:\n",
    "            if nums1[i]>nums2[j]:\n",
    "                sum2+=nums2[j]\n",
    "                j=j+1\n",
    "            elif nums1[i]<nums2[j]:\n",
    "                sum1+=nums1[i]\n",
    "                i=i+1\n",
    "            elif nums1[i]==nums2[j]:\n",
    "                t=(max(sum1,sum2)+nums1[i])%mod\n",
    "                sum1=t\n",
    "                sum2=t\n",
    "                i=i+1\n",
    "                j=j+1\n",
    "        sum1=sum1+sum(nums1[i:])\n",
    "        sum2=sum2+sum(nums2[j:])\n",
    "\n",
    "        return (max(sum1,sum2))%mod        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        left, right =0, 0\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        res = 0\n",
    "        sum1, sum2 = 0, 0\n",
    "        while left < m or right < n:\n",
    "            if right >= n or (left < m and nums1[left] < nums2[right]):\n",
    "                sum1 += nums1[left]\n",
    "                left += 1\n",
    "            elif right < n and left < m and nums1[left] == nums2[right]:\n",
    "                if sum1 > sum2:\n",
    "                    res += sum1 + nums1[left]\n",
    "                else:\n",
    "                    res += sum2 + nums1[left]\n",
    "                right += 1\n",
    "                left += 1\n",
    "                sum1 = sum2 = 0\n",
    "            else:\n",
    "                sum2 += nums2[right]\n",
    "                right += 1\n",
    "        if sum1 > sum2:\n",
    "            res += sum1\n",
    "        else:\n",
    "            res += sum2\n",
    "        return res % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        sum1,sum2,i,j,INF=0,0,0,0,int(math.pow(10,9)+7)\n",
    "        while i<len(nums1) and j<len(nums2):\n",
    "            if nums1[i]<nums2[j]:\n",
    "                sum1 +=nums1[i]\n",
    "                i +=1\n",
    "            elif nums2[j]<nums1[i]:\n",
    "                sum2 +=nums2[j]\n",
    "                j +=1\n",
    "            else:\n",
    "                sum1=sum2=(max(sum1,sum2)+nums1[i]) % INF\n",
    "                i +=1\n",
    "                j +=1\n",
    "        sum1,sum2=sum1+sum(nums1[i:]),sum2+sum(nums2[j:])\n",
    "        return max(sum1,sum2)%INF\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        i = j = sum1 = sum2 = 0\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        res = 0\n",
    "        while i < n1 and j < n2:\n",
    "            if nums1[i] == nums2[j]:\n",
    "                res += max(sum1, sum2) + nums1[i]\n",
    "                i += 1\n",
    "                j += 1\n",
    "                sum1 = sum2 = 0\n",
    "            elif nums1[i] < nums2[j]:\n",
    "                sum1 += nums1[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                sum2 += nums2[j]\n",
    "                j += 1\n",
    "        while i < n1:\n",
    "            sum1 += nums1[i]\n",
    "            i += 1\n",
    "        while j < n2:\n",
    "            sum2 += nums2[j]\n",
    "            j += 1\n",
    "        res += max(sum1, sum2)\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        best1 = best2 = 0\n",
    "        i = j = 0\n",
    "        while i < m or j < n:\n",
    "            if i < m and j < n:\n",
    "                if nums1[i] < nums2[j]:\n",
    "                    best1 += nums1[i]\n",
    "                    i += 1\n",
    "                elif nums1[i] > nums2[j]:\n",
    "                    best2 += nums2[j]\n",
    "                    j += 1\n",
    "                else:\n",
    "                    best = max(best1, best2) + nums1[i]\n",
    "                    best1 = best2 = best\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "            elif i < m:\n",
    "                best1 += nums1[i]\n",
    "                i += 1\n",
    "            elif j < n:\n",
    "                best2 += nums2[j]\n",
    "                j += 1\n",
    "        \n",
    "        return max(best1, best2) % mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        best1 = best2 = 0\n",
    "        i = j = 0\n",
    "        while i < m or j < n:\n",
    "            if i < m and j < n:\n",
    "                if nums1[i] < nums2[j]:\n",
    "                    best1 += nums1[i]\n",
    "                    i += 1\n",
    "                elif nums1[i] > nums2[j]:\n",
    "                    best2 += nums2[j]\n",
    "                    j += 1\n",
    "                else:\n",
    "                    best = max(best1, best2) + nums1[i]\n",
    "                    best1 = best2 = best\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "            elif i < m:\n",
    "                best1 += nums1[i]\n",
    "                i += 1\n",
    "            elif j < n:\n",
    "                best2 += nums2[j]\n",
    "                j += 1\n",
    "        \n",
    "        return max(best1, best2) % mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mod=1000000007\n",
    "        m,n=len(nums1),len(nums2)\n",
    "        dp1,dp2=0,0\n",
    "        i,j=1,1\n",
    "        while i<=m and j<=n:\n",
    "            if nums1[i-1]<nums2[j-1]:\n",
    "                dp1=dp1+nums1[i-1]\n",
    "                i+=1\n",
    "            elif nums1[i-1]>nums2[j-1]:\n",
    "                dp2=dp2+nums2[j-1]\n",
    "                j+=1\n",
    "            else:\n",
    "                cmax=max(dp1,dp2)+nums1[i-1]\n",
    "                dp1=dp2=cmax\n",
    "                i,j=i+1,j+1\n",
    "        while i<=m:\n",
    "            dp1=dp1+nums1[i-1]\n",
    "            i+=1\n",
    "        while j<=n:\n",
    "            dp2=dp2+nums2[j-1]\n",
    "            j+=1\n",
    "        return max(dp1,dp2) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        a, b = 0, 0\n",
    "        n, m = len(nums1), len(nums2)\n",
    "        i, j = 0, 0\n",
    "        while i < n or j < m:\n",
    "            if i < n and j < m:\n",
    "                if nums1[i] < nums2[j]:\n",
    "                    a += nums1[i]\n",
    "                    i += 1\n",
    "                elif nums1[i] > nums2[j]:\n",
    "                    b += nums2[j]\n",
    "                    j += 1\n",
    "                else:\n",
    "                    t = max(a, b) + nums1[i]\n",
    "                    a = b = t\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "            elif i < n:\n",
    "                a += nums1[i]\n",
    "                i += 1\n",
    "            elif j < m:\n",
    "                b += nums2[j]\n",
    "                j += 1\n",
    "        return max(a, b) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        v1, v2 = 0, 0\n",
    "        i, j = 0, 0\n",
    "\n",
    "        while i < m and j < n:\n",
    "            if nums1[i] < nums2[j]:\n",
    "                v1 += nums1[i]\n",
    "                i += 1\n",
    "            elif nums1[i] > nums2[j]:\n",
    "                v2 += nums2[j]\n",
    "                j += 1\n",
    "            else:\n",
    "                v1 = v2 = max(v1, v2) + nums1[i]\n",
    "                i += 1\n",
    "                j += 1\n",
    "        \n",
    "        while i < m:\n",
    "            v1 += nums1[i]\n",
    "            i += 1\n",
    "        while j < n:\n",
    "            v2 += nums2[j]\n",
    "            j += 1\n",
    "        \n",
    "        return max(v1, v2) % mod\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n=len(nums1), len(nums2)\n",
    "        i, j=0,0\n",
    "        best1,best2=0,0\n",
    "        while i<m or j<n:\n",
    "            if i<m and j<n:\n",
    "                if nums1[i]<nums2[j]:\n",
    "                    best1+=nums1[i]\n",
    "                    i+=1\n",
    "                elif nums1[i]>nums2[j]:\n",
    "                    best2+=nums2[j]\n",
    "                    j+=1\n",
    "                else:\n",
    "                    best=max(best1, best2)+nums1[i]\n",
    "                    best1=best2=best\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "            elif i<m:\n",
    "                best1+=nums1[i]\n",
    "                i+=1\n",
    "            elif j<n:\n",
    "                best2+=nums2[j]\n",
    "                j+=1\n",
    "        return max(best1, best2) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        best1 = best2 = 0\n",
    "        i = j = 0\n",
    "        while i < m or j < n:\n",
    "            if i < m and j < n:\n",
    "                if nums1[i] < nums2[j]:\n",
    "                    best1 += nums1[i]\n",
    "                    i += 1\n",
    "                elif nums1[i] > nums2[j]:\n",
    "                    best2 += nums2[j]\n",
    "                    j += 1\n",
    "                else:\n",
    "                    best = max(best1, best2) + nums1[i]\n",
    "                    best1 = best2 = best\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "            elif i < m:\n",
    "                best1 += nums1[i]\n",
    "                i += 1\n",
    "            elif j < n:\n",
    "                best2 += nums2[j]\n",
    "                j += 1\n",
    "        \n",
    "        return max(best1, best2) % mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        a = b = 0\n",
    "        i = j = 0\n",
    "        n = len(nums1)\n",
    "        m = len(nums2)\n",
    "        while i < n or j < m:\n",
    "            if i < n and j < m:\n",
    "                if nums1[i] < nums2[j]:\n",
    "                    a += nums1[i]\n",
    "                    i += 1\n",
    "                elif nums1[i] > nums2[j]:\n",
    "                    b += nums2[j]\n",
    "                    j += 1\n",
    "                else:\n",
    "                    t = max(a, b) + nums1[i]\n",
    "                    a = b = t\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "            elif i < n:\n",
    "                a += nums1[i]\n",
    "                i += 1\n",
    "            elif j < m:\n",
    "                b += nums2[j]\n",
    "                j += 1\n",
    "        return max(a, b) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        i, j, sum1, sum2, res = 0, 0, 0, 0, 0\n",
    "        n, m = len(nums1), len(nums2)\n",
    "        while i < n and j < m:\n",
    "            if nums1[i] == nums2[j]:\n",
    "                res += nums1[i]\n",
    "                res += max(sum1, sum2)\n",
    "                sum1, sum2 = 0, 0\n",
    "                i, j = i + 1, j + 1\n",
    "            elif nums1[i] > nums2[j]:\n",
    "                sum2 += nums2[j]\n",
    "                j += 1\n",
    "            else:\n",
    "                sum1 += nums1[i]\n",
    "                i += 1\n",
    "        \n",
    "        while i < n:\n",
    "            sum1 += nums1[i]\n",
    "            i += 1\n",
    "        \n",
    "        while j < m:\n",
    "            sum2 += nums2[j]\n",
    "            j += 1\n",
    "        \n",
    "        res += max(sum1, sum2)\n",
    "\n",
    "        return res % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        best1 = best2 = 0\n",
    "        i = j = 0\n",
    "        while i < m or j < n:\n",
    "            if i < m and j < n:\n",
    "                if nums1[i] < nums2[j]:\n",
    "                    best1 += nums1[i]\n",
    "                    i += 1\n",
    "                elif nums1[i] > nums2[j]:\n",
    "                    best2 += nums2[j]\n",
    "                    j += 1\n",
    "                else:\n",
    "                    best = max(best1, best2) + nums1[i]\n",
    "                    best1 = best2 = best\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "            elif i < m:\n",
    "                best1 += nums1[i]\n",
    "                i += 1\n",
    "            elif j < n:\n",
    "                best2 += nums2[j]\n",
    "                j += 1\n",
    "        \n",
    "        return max(best1, best2) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        count1=0\n",
    "        count2=0\n",
    "        max1=0\n",
    "    \n",
    "        i=0\n",
    "        j=0\n",
    "        \n",
    "        temp1=0\n",
    "        temp2=0\n",
    "        while  i<len(nums1) or j<len(nums2):\n",
    "            if i>=len(nums1): \n",
    "                count2+=nums2[j]\n",
    "                j+=1\n",
    "            elif j>=len(nums2):\n",
    "                count1+=nums1[i]\n",
    "                i+=1\n",
    "            else:\n",
    "                temp1=nums1[i]\n",
    "                temp2=nums2[j]\n",
    "                \n",
    "                if temp1<temp2 :\n",
    "                    count1+=temp1\n",
    "                    i+=1\n",
    "                elif temp1>temp2 :\n",
    "                    count2+=temp2\n",
    "                    j+=1\n",
    "                \n",
    "                else:\n",
    "                    max1=temp1+max1+max(count1,count2)\n",
    "                    count1=0\n",
    "                    count2=0\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "            \n",
    "                \n",
    "\n",
    "\n",
    "        max1=max(count1,count2)+max1\n",
    "        c=10**9+7\n",
    "        return max1%c\n",
    "\n",
    "\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mod=10**9+7\n",
    "        m,n=len(nums1),len(nums2)\n",
    "        best1=best2=0\n",
    "        i=j=0\n",
    "        while i<m or j<n:\n",
    "            if i<m and j<n:\n",
    "                if nums1[i]<nums2[j]:\n",
    "                    best1+=nums1[i]\n",
    "                    i+=1\n",
    "                elif nums1[i]>nums2[j]:\n",
    "                    best2+=nums2[j]\n",
    "                    j+=1\n",
    "                else:\n",
    "                    best=max(best1,best2)+nums1[i]\n",
    "                    best1=best2=best\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "            elif i<m:\n",
    "                best1+=nums1[i]\n",
    "                i+=1\n",
    "            elif j<n:\n",
    "                best2+=nums2[j]\n",
    "                j+=1\n",
    "\n",
    "        return max(best1, best2) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        i = j = 0\n",
    "        ans = 0\n",
    "        cnt1 = cnt2 = 0\n",
    "        while i < n1 and j < n2:\n",
    "            if nums1[i] < nums2[j]:\n",
    "                cnt1 += nums1[i]\n",
    "                i += 1\n",
    "            elif nums1[i] > nums2[j]:\n",
    "                cnt2 += nums2[j]\n",
    "                j += 1\n",
    "            else:\n",
    "                ans += max(cnt1, cnt2) + nums1[i]\n",
    "                cnt1 = cnt2 = 0\n",
    "                i += 1\n",
    "                j += 1\n",
    "        while i < n1:\n",
    "            cnt1 += nums1[i]\n",
    "            i += 1\n",
    "        while j < n2:\n",
    "            cnt2 += nums2[j]\n",
    "            j += 1\n",
    "        ans += max(cnt1, cnt2)\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        best1=0\n",
    "        best2=0\n",
    "        i=0\n",
    "        j=0\n",
    "        m=len(nums1)\n",
    "        n=len(nums2)\n",
    "        while i<m or j<n:\n",
    "            if i<m and j<n:\n",
    "                if nums1[i]>nums2[j]:\n",
    "                    best2+=nums2[j]\n",
    "                    j+=1\n",
    "                elif nums1[i]<nums2[j]:\n",
    "                    best1+=nums1[i]\n",
    "                    i+=1\n",
    "                else:\n",
    "                    best=max(best1,best2)+nums1[i]\n",
    "                    best1=best2=best\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "            elif i<m:\n",
    "                best1+=nums1[i]\n",
    "                i+=1\n",
    "            else:\n",
    "                best2+=nums2[j]\n",
    "                j+=1\n",
    "        return int(max(best1,best2) % (1e9+7))\n",
    "    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2) \n",
    "        mx1,mx2 = nums1[0], nums2[0] \n",
    "        i, j= 0, 0 \n",
    "        Mod = int(1e9+7)\n",
    "        while i < m and j < n:\n",
    "            if nums1[i] > nums2[j]:\n",
    "                j+=1\n",
    "                if j < n:\n",
    "                    mx2 += nums2[j]\n",
    "            elif nums1[i] < nums2[j]:\n",
    "                i+=1\n",
    "                if i < m:\n",
    "                    mx1 += nums1[i]\n",
    "            else:\n",
    "                mx = max(mx1, mx2)\n",
    "                mx1 = mx2 = mx \n",
    "                i+=1 \n",
    "                if i < m:\n",
    "                    mx1 += nums1[i] \n",
    "        i+=1\n",
    "        while i < m:\n",
    "            mx1 += nums1[i]\n",
    "            i+=1\n",
    "        j+=1\n",
    "        while j < n:\n",
    "            mx2 += nums2[j]\n",
    "            j+=1\n",
    "        return max(mx1, mx2) % Mod "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        midset1 = set(nums1)\n",
    "        midset2 = set(nums2)\n",
    "        midlst = list(\n",
    "        midset1.intersection(midset2))\n",
    "        if not midlst:\n",
    "            return max(sum(nums1),sum(nums2))\n",
    "        midlst.sort()\n",
    "        ans = sum(midlst)\n",
    "        lastpos1 = lastpos2 = -1\n",
    "        tmp1 = tmp2 = 0\n",
    "        for i in range(len(midlst)):\n",
    "            pos1 = nums1.index(midlst[i])\n",
    "            pos2 = nums2.index(midlst[i])\n",
    "            \n",
    "            if pos1 == 0:\n",
    "                tmp1 = 0\n",
    "            else:\n",
    "                tmp1 = sum(nums1[lastpos1+1:pos1]) \n",
    "            lastpos1 = pos1\n",
    "            \n",
    "            if pos2 == 0:\n",
    "                tmp2 = 0\n",
    "            else:\n",
    "                tmp2 = sum(nums2[lastpos2+1:pos2])  \n",
    "            lastpos2 = pos2\n",
    "            \n",
    "            ans += max(tmp1,tmp2)\n",
    "            if i == len(midlst) - 1:\n",
    "                tmp1 = sum(nums1[pos1+1:]) \n",
    "                tmp2 = sum(nums2[pos2+1:]) \n",
    "                ans += max(tmp1,tmp2)\n",
    "        #return ans\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        midset1 = set(nums1)\n",
    "        midset2 = set(nums2)\n",
    "        midlst = list(\n",
    "        midset1.intersection(midset2))\n",
    "        if not midlst:\n",
    "            return max(sum(nums1),sum(nums2))\n",
    "        midlst.sort()\n",
    "        ans = sum(midlst)\n",
    "        lastpos1 = lastpos2 = -1\n",
    "        tmp1 = tmp2 = 0\n",
    "        for i in range(len(midlst)):\n",
    "            pos1 = nums1.index(midlst[i])\n",
    "            pos2 = nums2.index(midlst[i])\n",
    "            \n",
    "            if pos1 == 0:\n",
    "                tmp1 = 0\n",
    "            else:\n",
    "                tmp1 = sum(nums1[lastpos1+1:pos1]) \n",
    "            lastpos1 = pos1\n",
    "            \n",
    "            if pos2 == 0:\n",
    "                tmp2 = 0\n",
    "            else:\n",
    "                tmp2 = sum(nums2[lastpos2+1:pos2])  \n",
    "            lastpos2 = pos2\n",
    "            \n",
    "            ans += max(tmp1,tmp2)\n",
    "            if i == len(midlst) - 1:\n",
    "                tmp1 = sum(nums1[pos1+1:]) \n",
    "                tmp2 = sum(nums2[pos2+1:]) \n",
    "                ans += max(tmp1,tmp2)\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "\n",
    "        MODX = 10**9+7\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        n1,n2 = len(nums1),len(nums2)\n",
    "\n",
    "        \n",
    "        dp1 = [0]*(n1+1) \n",
    "        dp2 = [0]*(n2+1)\n",
    "        i,j =0,0 \n",
    "\n",
    "        while i<n1 and j<n2:\n",
    "            if nums1[i]==nums2[j]:\n",
    "                dp1[i+1] = (max(dp1[i]+nums1[i], dp2[j]+nums2[j]) )%MODX\n",
    "                dp2[j+1] = (max(dp1[i]+nums1[i],dp2[j]+nums2[j]))%MODX\n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif nums1[i]>nums2[j]:\n",
    "      \n",
    "                dp2[j+1] = dp2[j]+nums2[j]\n",
    "                j += 1\n",
    "            elif nums2[j]>nums1[i]:\n",
    "                dp1[i+1] = dp1[i]+nums1[i]\n",
    "\n",
    "                i += 1\n",
    "        \n",
    "        if i<n1:\n",
    "            while i<n1:\n",
    "                dp1[i+1]= dp1[i]+nums1[i]\n",
    "                i += 1 \n",
    "        if j<n2:\n",
    "            while j<n2:\n",
    "                dp2[j+1] = dp2[j]+nums2[j]\n",
    "                j += 1\n",
    "        \n",
    "        return max(dp1[-1],dp2[-1])%MODX\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ls1=[]\n",
    "        ls2=[]\n",
    "        mod=10**9+7\n",
    "        ls=sorted(list(set(nums1)&set(nums2)))\n",
    "        if len(ls)==0:\n",
    "            return max(sum(nums1),sum(nums2))\n",
    "        #print(ls)\n",
    "        #s1,s2=0,0\n",
    "        l,r=0,-1\n",
    "        for k in ls:\n",
    "            #print(k)\n",
    "            l=r+1\n",
    "            r=bisect_left(nums1,k)\n",
    "            ls1.append(sum(nums1[l:r]))\n",
    "            #print(l,r)\n",
    "        l=r+1\n",
    "        ls1.append(sum(nums1[l:]))\n",
    "        #print(ls1)\n",
    "        l,r=0,-1\n",
    "        for k in ls:\n",
    "            #print(k)\n",
    "            l=r+1\n",
    "            r=bisect_left(nums2,k)\n",
    "            ls2.append(sum(nums2[l:r]))\n",
    "            #print(l,r)\n",
    "        l=r+1\n",
    "        ls2.append(sum(nums2[l:]))\n",
    "        #print(ls2)\n",
    "        ans=0\n",
    "        for i in range(len(ls1)):\n",
    "            a,b=ls1[i],ls2[i]\n",
    "            if a>b:\n",
    "                ans+=a\n",
    "            else:\n",
    "                ans+=b\n",
    "        ans+=sum(ls)\n",
    "        return ans%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        d = {t: i for i, t in enumerate(nums1)}\n",
    "        ans = 0\n",
    "        p, q = 0, 0\n",
    "        for j, t in enumerate(nums2):\n",
    "            if t in d:\n",
    "                i = d[t]\n",
    "                ans += max(sum(nums1[p: i]), sum(nums2[q: j]))\n",
    "                p, q = i, j\n",
    "        ans += max(sum(nums1[p: ]), sum(nums2[q: ]))\n",
    "        return ans % 1000000007\n",
    "\n",
    "    \n",
    "    def maxSum2(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        d1 = {t: i for i, t in enumerate(nums1)}\n",
    "        d2 = {t: j for j, t in enumerate(nums2)}\n",
    "        ans = 0\n",
    "        p, q = 0, 0\n",
    "        for t in sorted({*nums1} & {*nums2}):\n",
    "            i, j = d1[t], d2[t]\n",
    "            ans += max(sum(nums1[p: i]), sum(nums2[q: j]))\n",
    "            p, q = i, j\n",
    "        ans += max(sum(nums1[p: ]), sum(nums2[q: ]))\n",
    "        return ans % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        set1 = {}\n",
    "        for i in range(len(nums1)):\n",
    "            set1[nums1[i]] = i\n",
    "        pre = (0,0)\n",
    "        res = 0\n",
    "        for i in range(len(nums2)):\n",
    "            if nums2[i] in set1:\n",
    "                res += max(sum(nums1[pre[0]: set1[nums2[i]]+1]), sum(nums2[pre[1]: i+1]))\n",
    "                res %= int(1e9+7)\n",
    "                pre = (set1[nums2[i]]+1, i+1)\n",
    "        res += max(sum(nums1[pre[0]:]), sum(nums2[pre[1]:]))\n",
    "        res %= int(1e9+7)\n",
    "        return res\n",
    "        # global rres\n",
    "        # rres = 0\n",
    "\n",
    "        # def recursion(idx, flag, path, res):\n",
    "        #     global rres\n",
    "        #     if flag == 1:\n",
    "        #         path.add(nums1[idx])\n",
    "        #         res += nums1[idx]\n",
    "        #         idx += 1\n",
    "        #         while(idx<len(nums1)):\n",
    "        #             if nums1[idx] in sset and nums1[idx] not in path:\n",
    "        #                 recursion(sset[nums1[idx]][1], 2, path.copy(), res)\n",
    "        #             if nums1[idx] not in path:\n",
    "        #                 res += nums1[idx]\n",
    "        #                 path.add(nums1[idx])\n",
    "        #             idx += 1\n",
    "        #     if flag == 2:\n",
    "        #         path.add(nums2[idx])\n",
    "        #         res += nums2[idx]\n",
    "        #         idx += 1\n",
    "        #         while(idx<len(nums2)):\n",
    "        #             if nums2[idx] in sset and nums2[idx] not in path:\n",
    "        #                 recursion(sset[nums2[idx]][0], 1, path.copy(), res)\n",
    "        #             if nums2[idx] not in path:\n",
    "        #                 res += nums2[idx]\n",
    "        #                 path.add(nums2[idx])\n",
    "        #             idx += 1\n",
    "        #     rres = max(rres, res)\n",
    "        # recursion(0, 1, set(), 0)\n",
    "        # recursion(0, 2, set(), 0)\n",
    "        # return rres\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        set1 = {}\n",
    "        for i in range(len(nums1)):\n",
    "            set1[nums1[i]] = i\n",
    "        pre = (0,0)\n",
    "        res = 0\n",
    "        for i in range(len(nums2)):\n",
    "            if nums2[i] in set1:\n",
    "                res += max(sum(nums1[pre[0]: set1[nums2[i]]+1]), sum(nums2[pre[1]: i+1]))\n",
    "                res %= int(1e9+7)\n",
    "                pre = (set1[nums2[i]]+1, i+1)\n",
    "        res += max(sum(nums1[pre[0]:]), sum(nums2[pre[1]:]))\n",
    "        res %= int(1e9+7)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        set1 = {}\n",
    "        for i in range(len(nums1)):\n",
    "            set1[nums1[i]] = i\n",
    "        pre = (0,0)\n",
    "        res = 0\n",
    "        for i in range(len(nums2)):\n",
    "            if nums2[i] in set1:\n",
    "                res += max(sum(nums1[pre[0]: set1[nums2[i]]+1]), sum(nums2[pre[1]: i+1]))\n",
    "                res %= int(1e9+7)\n",
    "                pre = (set1[nums2[i]]+1, i+1)\n",
    "        res += max(sum(nums1[pre[0]:]), sum(nums2[pre[1]:]))\n",
    "        res %= int(1e9+7)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "from string import *\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1,n2 = len(nums1),len(nums2)\n",
    "        d1,d2 = 0, 0\n",
    "        dp1,dp2 = [0] * (n1+1),[0] * (n2+1)\n",
    "        while d1 < n1 and d2 < n2:\n",
    "            if nums1[d1] == nums2[d2]:\n",
    "                dp1[d1+1] = dp2[d2+1] = max(dp1[d1], dp2[d2]) + nums1[d1]\n",
    "                d1 += 1\n",
    "                d2 += 1\n",
    "            elif nums1[d1] < nums2[d2]:\n",
    "                dp1[d1+1] = dp1[d1] + nums1[d1]\n",
    "                d1 += 1\n",
    "            else:\n",
    "                dp2[d2+1] = dp2[d2] + nums2[d2]\n",
    "                d2 += 1\n",
    "        while d1 < n1 :\n",
    "            dp1[d1+1] = dp1[d1] + nums1[d1]\n",
    "            d1 += 1\n",
    "        while d2 < n2:\n",
    "            dp2[d2+1] = dp2[d2] + nums2[d2]\n",
    "            d2 += 1\n",
    "        return max(dp1[n1],dp2[n2]) % 1000000007\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        走完整条路径后所获得的最大和\n",
    "        Args:\n",
    "            nums1 (list[int]): 原始递增数组1\n",
    "            nums2 (list[int]): 原始递增数组2\n",
    "        returns (int): 最大的路径和\n",
    "        \"\"\"\n",
    "        #处理异常情况\n",
    "        if nums1 == None or nums2 == None:\n",
    "            return 0  \n",
    "        \n",
    "        MOD = 1e9 + 7\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        #f[i], g[j]的定义, 分别表示到达nums1[...i]位置处所能够获得的最大路径和, nums2[...j]处所能够获得的最大路径和\n",
    "        f = [0 for _ in range(m + 1)]\n",
    "        g = [0 for _ in range(n + 1)]\n",
    "    \n",
    "\n",
    "        i, j = 0, 0     #分别指向nums1, nums2的索引\n",
    "\n",
    "        #遍历方向采用类似于归并排序的方法\n",
    "        while i < m and j < n:\n",
    "            #case1. 当nums1[i] != nums2[j]时, f[i], g[j]只能从前一个状态得到\n",
    "            #case2. 当nums1[i] == nums2[j]时, f[i] = g[j] = max(f[i-1], g[j-1]) + nums1[i], i += 1, j += 1\n",
    "            if nums1[i] < nums2[j]:\n",
    "                f[i + 1] = f[i] + nums1[i]\n",
    "                i += 1\n",
    "\n",
    "            elif nums1[i] > nums2[j]:\n",
    "                g[j + 1] = g[j] + nums2[j]\n",
    "                j += 1\n",
    "\n",
    "            else:\n",
    "                f[i + 1] = g[j + 1] = max(g[j], f[i]) + nums1[i]\n",
    "                i += 1\n",
    "                j += 1\n",
    "        \n",
    "        while i < m:\n",
    "            f[i + 1] = f[i] + nums1[i] \n",
    "            i += 1\n",
    "        \n",
    "        while j < n:\n",
    "            g[j + 1] = g[j] + nums2[j]\n",
    "            j += 1\n",
    "\n",
    "        #return\n",
    "        return int(max(f[-1], g[-1]) % MOD)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "\n",
    "        from collections import defaultdict\n",
    "        dic_1 = defaultdict(int)\n",
    "        \n",
    "        for idx, value in enumerate(nums1):\n",
    "            dic_1[value] = idx\n",
    "        index1 = []\n",
    "        index2 = []\n",
    "        for idx, num in enumerate(nums2):\n",
    "            if num in dic_1:\n",
    "                index1.append(dic_1[num])\n",
    "                index2.append(idx)\n",
    "        index1.append(len(nums1)-1)\n",
    "        index2.append(len(nums2)-1)\n",
    "        left1 = 0\n",
    "        left2 = 0\n",
    "        res = 0\n",
    "        while index1:\n",
    "            idx1 = index1.pop(0)\n",
    "            idx2 = index2.pop(0)\n",
    "            temp1 = 0\n",
    "            temp2 = 0\n",
    "            for i in range(left1,idx1+1):\n",
    "               temp1 += nums1[i]\n",
    "            left1 = idx1 + 1\n",
    "            for i in range(left2, idx2 + 1):\n",
    "                temp2 += nums2[i]\n",
    "            left2 = idx2 + 1\n",
    "            res += max(temp1,temp2)\n",
    "        return res %(10**9+7)\n",
    "             \n",
    "                \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\r\n",
    "        # mp1 = {x: i for i, x in enumerate(nums1)}\r\n",
    "        # mp2 = {x: i for i, x in enumerate(nums2)}\r\n",
    "        m, n = len(nums1), len(nums2)\r\n",
    "        dp1 = [0] * (len(nums1) + 1)\r\n",
    "        dp2 = [0] * (len(nums2) + 1)\r\n",
    "        i, j = 0, 0 \r\n",
    "        while i < m and j < n:\r\n",
    "            if nums1[i] < nums2[j]:\r\n",
    "                dp1[i + 1] = dp1[i] + nums1[i]\r\n",
    "                i += 1 \r\n",
    "            elif nums1[i] > nums2[j]:\r\n",
    "                dp2[j + 1] = dp2[j] + nums2[j]\r\n",
    "                j += 1 \r\n",
    "            else:\r\n",
    "                # 相等\r\n",
    "                dp1[i + 1] = max(dp1[i], dp2[j]) + nums1[i]\r\n",
    "                dp2[j + 1] = max(dp1[i], dp2[j]) + nums1[i]\r\n",
    "                i += 1\r\n",
    "                j += 1 \r\n",
    "        while i < m:\r\n",
    "            dp1[i + 1] = dp1[i] + nums1[i]\r\n",
    "            i += 1\r\n",
    "        while j < n:\r\n",
    "            dp2[j + 1] = dp2[j] + nums2[j]\r\n",
    "            j += 1 \r\n",
    "        # print(dp1)\r\n",
    "        # print(dp2)\r\n",
    "        return max(dp1[-1], dp2[-1]) % (10 ** 9 + 7)\r\n",
    "             \r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "\n",
    "        MODX = 10**9+7\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        n1,n2 = len(nums1),len(nums2)\n",
    "\n",
    "        \n",
    "        dp1 = [0]*(n1+1) \n",
    "        dp2 = [0]*(n2+1)\n",
    "        i,j =0,0 \n",
    "\n",
    "        while i<n1 and j<n2:\n",
    "            if nums1[i]==nums2[j]:\n",
    "                dp1[i+1] = max(dp1[i]+nums1[i], dp2[j]+nums2[j])\n",
    "                dp2[j+1] = max(dp1[i]+nums1[i],dp2[j]+nums2[j])\n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif nums1[i]>nums2[j]:\n",
    "      \n",
    "                dp2[j+1] = dp2[j]+nums2[j]\n",
    "                j += 1\n",
    "            elif nums2[j]>nums1[i]:\n",
    "                dp1[i+1] = dp1[i]+nums1[i]\n",
    "\n",
    "                i += 1\n",
    "        \n",
    "        if i<n1:\n",
    "            while i<n1:\n",
    "                dp1[i+1]= dp1[i]+nums1[i]\n",
    "                i += 1 \n",
    "        if j<n2:\n",
    "            while j<n2:\n",
    "                dp2[j+1] = dp2[j]+nums2[j]\n",
    "                j += 1\n",
    "        \n",
    "        return max(dp1[-1],dp2[-1])%MODX\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "                    \n",
    "                n = len(nums1)\n",
    "                m = len(nums2)\n",
    "                q = [(0,0)]\n",
    "                i,j = 0,0\n",
    "                while i < n and j < m:\n",
    "                    if nums1[i] < nums2[j]:\n",
    "                        i += 1\n",
    "                    elif nums1[i] > nums2[j]:\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        q.append((i,j))\n",
    "                        i += 1;j += 1\n",
    "                q.append((n - 1,m - 1))\n",
    "                ans = 0\n",
    "                s1 = [nums1[0]] * (n)\n",
    "                s2 = [nums2[0]] * (m)\n",
    "                for i in range(1,n):s1[i] = s1[i - 1] + nums1[i]\n",
    "                for j in range(1,m):s2[j] = s2[j - 1] + nums2[j]\n",
    "                    \n",
    "                first = True\n",
    "                for i,j in pairwise(q):\n",
    "                    i1,j1 = i\n",
    "                    i2,j2 = j\n",
    "                    a = s1[i2] - s1[i1] if not first else s1[i2]\n",
    "                    b = s2[j2] - s2[j1] if not first else s2[j2]\n",
    "                    ans += max(a,b)\n",
    "                    # print(i1,i2,j1,j2,a,b)\n",
    "                    first = False\n",
    "                return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # 前缀和，走最大的每段\n",
    "        mod = 10 ** 9 + 7\n",
    "        n1 = len(nums1)\n",
    "        n2 = len(nums2)\n",
    "        sum1 = [0] * (n1 + 1)\n",
    "        sum2 = [0] * (n2 + 1)\n",
    "        dic = {}\n",
    "        i = 0\n",
    "        j = 0\n",
    "\n",
    "        while i < n1 and j < n2:\n",
    "            if nums1[i] < nums2[j]:\n",
    "                sum1[i + 1] = sum1[i] + nums1[i]\n",
    "                i += 1\n",
    "            elif nums1[i] > nums2[j]:\n",
    "                sum2[j + 1] = sum2[j] + nums2[j]\n",
    "                j += 1\n",
    "            else:\n",
    "                dic[i] = j\n",
    "                sum1[i + 1] = sum1[i] + nums1[i]\n",
    "                sum2[j + 1] = sum2[j] + nums2[j]\n",
    "                i += 1\n",
    "                j += 1\n",
    "        \n",
    "        if i != n1:\n",
    "            while i < n1:\n",
    "                sum1[i + 1] = sum1[i] + nums1[i]\n",
    "                i += 1\n",
    "\n",
    "        if j != n2:\n",
    "            while j < n2:\n",
    "                sum2[j + 1] = sum2[j] + nums2[j]\n",
    "                j += 1                                \n",
    "        \n",
    "        dic[n1 - 1] = n2 - 1\n",
    "        prev1 = 0\n",
    "        prev2 = 0\n",
    "        maximum = 0\n",
    "        for key, val in dic.items():\n",
    "            cur1 = sum1[key + 1]\n",
    "            cur2 = sum2[val + 1]\n",
    "            maximum = max(cur1 - prev1, cur2 - prev2) + maximum\n",
    "            prev1 = cur1\n",
    "            prev2 = cur2\n",
    "\n",
    "        return maximum % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        s1, s2 = list(accumulate(nums1, initial = 0)), list(accumulate(nums2, initial = 0))\n",
    "        eqidx = []\n",
    "        i, j, n, m = 0, 0, len(nums1), len(nums2)\n",
    "        while i < n and j < m:\n",
    "            if nums1[i] == nums2[j]:\n",
    "                eqidx.append([i, j])\n",
    "            if nums1[i] > nums2[j]:\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        eqidx.append([n-1, m-1])\n",
    "        ans = 0\n",
    "        p1 = p2 = -1\n",
    "        for idx1, idx2 in eqidx:\n",
    "            part1 = s1[idx1 + 1] - s1[p1 + 1]\n",
    "            part2 = s2[idx2 + 1] - s2[p2 + 1]\n",
    "            ans += max(part1, part2)\n",
    "            ans %= MOD\n",
    "            p1, p2 = idx1, idx2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "\n",
    "        MODX = 10**9+7\n",
    "\n",
    "        index1 = dict()\n",
    "        index2 = dict()\n",
    "\n",
    "        i,j=0,0\n",
    "        n1,n2 = len(nums1),len(nums2)\n",
    "        while i<n1 and j<n2:\n",
    "            if nums1[i]==nums2[j]:\n",
    "                index1[i] = j\n",
    "                index2[j] = i \n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif nums1[i]>nums2[j]:\n",
    "                j += 1\n",
    "            elif nums1[i]<nums2[j]:\n",
    "                i += 1\n",
    "        \n",
    "        dp1 = [0]*(n1+1) \n",
    "        dp2 = [0]*(n2+1)\n",
    "        i,j =0,0 \n",
    "\n",
    "        while i<n1 and j<n2:\n",
    "            if nums1[i]==nums2[j]:\n",
    "                dp1[i+1] = max(dp1[i]+nums1[i], dp2[j]+nums2[j])\n",
    "                dp2[j+1] = max(dp1[i]+nums1[i],dp2[j]+nums2[j])\n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif nums1[i]>nums2[j]:\n",
    "      \n",
    "                dp2[j+1] = dp2[j]+nums2[j]\n",
    "                j += 1\n",
    "            elif nums2[j]>nums1[i]:\n",
    "                dp1[i+1] = dp1[i]+nums1[i]\n",
    "\n",
    "                i += 1\n",
    "        \n",
    "        if i<n1:\n",
    "            while i<n1:\n",
    "                dp1[i+1]= dp1[i]+nums1[i]\n",
    "                i += 1 \n",
    "        if j<n2:\n",
    "            while j<n2:\n",
    "                dp2[j+1] = dp2[j]+nums2[j]\n",
    "                j += 1\n",
    "        \n",
    "        return max(dp1[-1],dp2[-1])%MODX\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mx = max(nums1[-1], nums2[-1]) + 1\n",
    "        nums1 = [0] + nums1 + [mx]\n",
    "        nums2 = [0] + nums2 + [mx]\n",
    "        mp = {x:i for i,x in enumerate(nums2)}\n",
    "        a = []\n",
    "        for i, x in enumerate(nums1):\n",
    "            if x in mp:\n",
    "                a.append((i, mp[x]))\n",
    "        ans = 0\n",
    "        for (i1,j1),(i2,j2) in pairwise(a):\n",
    "            ans += max(sum(nums1[i1:i2]), sum(nums2[j1:j2]))\n",
    "        return ans % (10**9 + 7)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # 预处理，将所有的分段和求出来\n",
    "        commonSet = set(nums1) & set(nums2)  # 寻找两个列表的公共元素\n",
    "        dict1 = {value: index for index, value in enumerate(nums1)}\n",
    "        dict2 = {value:index for index,value in enumerate(nums2)}\n",
    "\n",
    "        def getTotal(nums_a,nums_b,my_dict):\n",
    "            total=0\n",
    "            idx=0\n",
    "            while idx<len(nums_a):\n",
    "                if nums_a[idx] in commonSet:\n",
    "                    num=nums_a[idx]\n",
    "                    curTotal1=num\n",
    "                    for i in range(idx+1,len(nums_a)):\n",
    "                        if nums_a[i] in commonSet:\n",
    "                            idx=i-1\n",
    "                            break\n",
    "                        curTotal1+=nums_a[i]\n",
    "                        if i==len(nums_a)-1:\n",
    "                            idx=i\n",
    "           \n",
    "                    idx2=my_dict[num]\n",
    "                    curTotal2=nums_b[idx2]\n",
    "                    for i in range(idx2+1,len(nums_b)):\n",
    "                        if nums_b[i] in commonSet:\n",
    "                            break\n",
    "                        curTotal2+=nums_b[i]\n",
    "                    total+=max(curTotal1,curTotal2)\n",
    "                else:\n",
    "                    total+=nums_a[idx]\n",
    "                idx+=1\n",
    "            return total\n",
    "        return max(getTotal(nums1,nums2,dict2),getTotal(nums2,nums1,dict1))%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "\n",
    "        '''\n",
    "        每一次相连的时候, 就计算上一次相连到这一次相连走2条路径分别增加了多少\n",
    "        使用前缀和来加快计算速度\n",
    "\n",
    "        为了使操作更简单, 假设nums1和nums2前面多了个0, 后面多了个10 ** 8\n",
    "        '''\n",
    "        big = 10 ** 8\n",
    "        nums1.append(big)\n",
    "        nums2.append(big)\n",
    "        \n",
    "        N1, N2 = len(nums1), len(nums2)\n",
    "        s1, s2 = set(nums1), set(nums2)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        \n",
    "        \n",
    "        # 假装nums1和nums2前面有个0\n",
    "        prefix1, prefix2 = [0,0], [0,0]\n",
    "        \n",
    "        for n in nums1:\n",
    "            prefix1.append(prefix1[-1] + n)\n",
    "        for n in nums2:\n",
    "            prefix2.append(prefix2[-1] + n)\n",
    "            \n",
    "        ans = 0\n",
    "        dup = 0\n",
    "        lst1 = lst2 = -1\n",
    "        \n",
    "        for i1 in range(len(nums1)):\n",
    "            n1 = nums1[i1]\n",
    "            if n1 in s2:\n",
    "                i2 = bisect_left(nums2, n1) # 找到这个数在nums2中的位置\n",
    "                ans += max(prefix1[i1+1]-prefix1[lst1+2], prefix2[i2+1]-prefix2[lst2+2]) # 上一次相连到这一次, 2条路径分别的和\n",
    "                dup += n1 # 将这些重复的数统计起来\n",
    "                \n",
    "                ans %= MOD\n",
    "                dup %= MOD\n",
    "                lst1 = i1\n",
    "                lst2 = i2\n",
    "                              \n",
    "        \n",
    "        \n",
    "        return (ans + (dup - big + MOD)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        big = 10 ** 8\n",
    "        nums1.append(big)\n",
    "        nums2.append(big)\n",
    "        \n",
    "        N1, N2 = len(nums1), len(nums2)\n",
    "        s1, s2 = set(nums1), set(nums2)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        \n",
    "        \n",
    "        # 假装nums1和nums2前面有个0\n",
    "        prefix1, prefix2 = [0,0], [0,0]\n",
    "        \n",
    "        for n in nums1:\n",
    "            prefix1.append(prefix1[-1] + n)\n",
    "        for n in nums2:\n",
    "            prefix2.append(prefix2[-1] + n)\n",
    "            \n",
    "        ans = 0\n",
    "        dup = 0\n",
    "        lst1 = lst2 = -1\n",
    "        \n",
    "        for i1 in range(len(nums1)):\n",
    "            n1 = nums1[i1]\n",
    "            if n1 in s2:\n",
    "                i2 = bisect_left(nums2, n1)\n",
    "                ans += max(prefix1[i1+1]-prefix1[lst1+2], prefix2[i2+1]-prefix2[lst2+2])\n",
    "                dup += n1\n",
    "                \n",
    "                ans %= MOD\n",
    "                dup %= MOD\n",
    "                lst1 = i1\n",
    "                lst2 = i2\n",
    "                              \n",
    "        \n",
    "        \n",
    "        return (ans + (dup - big + MOD)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        pre1,pre2={-1:0},{-1:0}\n",
    "        n1,n2=len(nums1),len(nums2)\n",
    "        s=0\n",
    "        for e in nums1:\n",
    "            s+=e\n",
    "            pre1[e]=s \n",
    "            \n",
    "        s=i=0\n",
    "        ans=0\n",
    "        last=-1\n",
    "        for i,e in enumerate(nums2):\n",
    "            s+=e\n",
    "            pre2[e]=s\n",
    "            if e in pre1:\n",
    "                #print('e',e,'v',max(pre1[e]-pre1[last],s-pre2[last]))\n",
    "                ans+=max(pre1[e]-pre1[last],s-pre2[last])\n",
    "                last=e\n",
    "            if i==n2-1:\n",
    "                ans+=max(pre1[nums1[-1]]-pre1[last],pre2[nums2[-1]]-pre2[last])\n",
    "            \n",
    "                \n",
    "        return ans%(10**9+7)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n=len(nums1)\n",
    "        m=len(nums2)\n",
    "\n",
    "        dic={}\n",
    "        node=[]\n",
    "        for i,x in enumerate(nums1):\n",
    "            dic[x]=i\n",
    "        for j,y in enumerate(nums2):\n",
    "            if y in dic:\n",
    "                node.append((dic[y],j,y))\n",
    "        if not node:\n",
    "            return max(sum(nums1),sum(nums2))\n",
    "        \n",
    "        s1=[nums1[0]]\n",
    "        s2=[nums2[0]]\n",
    "        for i in range(1,n):\n",
    "            s1.append(nums1[i]+s1[-1])\n",
    "        for i in range(1,m):\n",
    "            s2.append(nums2[i]+s2[-1])\n",
    "\n",
    "        ans=0\n",
    "        b_i=-1\n",
    "        b_j=-1\n",
    "        for o in node:\n",
    "            i=o[0]\n",
    "            j=o[1]\n",
    "            if b_i<0 or b_j<0:\n",
    "                ans+=max(s1[i],s2[j])\n",
    "            else:\n",
    "                ans+=max(s1[i]-s1[b_i],s2[j]-s2[b_j])\n",
    "            b_i=i\n",
    "            b_j=j\n",
    "        if b_i<n or b_j<m:\n",
    "            ans+=max(s1[-1]-s1[b_i],s2[-1]-s2[b_j])\n",
    "        return ans%(10**9+7)           \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        \n",
    "        mod = 10 ** 9 + 7\n",
    "        s1 = {num: i for i, num in enumerate(nums1)}\n",
    "        s2 = {num: i for i, num in enumerate(nums2)}\n",
    "        pres1 = list(accumulate(nums1, initial=0))\n",
    "        pres2 = list(accumulate(nums2, initial=0))\n",
    "        \n",
    "        changes = []\n",
    "        for num in nums1:\n",
    "            if num in s2:\n",
    "                changes.append(num)\n",
    "        \n",
    "        ans = max(sum(nums1), sum(nums2))\n",
    "        if changes:\n",
    "            num = changes[0]\n",
    "            \n",
    "            dp = [pres1[s1[num] + 1], pres2[s2[num] + 1]]\n",
    "            # print(dp)\n",
    "            for i in range(1, len(changes)):\n",
    "                pre = changes[i - 1]\n",
    "                pre1 = s1[pre]\n",
    "                pre2 = s2[pre]\n",
    "                num = changes[i]\n",
    "                idx1 = s1[num]\n",
    "                idx2 = s2[num]\n",
    "                tmp = dp[:]\n",
    "                tmp[0] = max(dp) + pres1[idx1 + 1] - pres1[pre1 + 1]\n",
    "                tmp[1] = max(dp) + pres2[idx2 + 1] - pres2[pre2 + 1]\n",
    "                dp = tmp\n",
    "           \n",
    "            end = changes[-1]\n",
    "            # dp[0] += pres1[-1] - pres1[s1[end] + 1]\n",
    "            # dp[1] += pres2[-1] - pres2[s2[end] + 1]\n",
    "            ans = max(ans, max(dp) + max(pres1[-1] - pres1[s1[end] + 1], pres2[-1] - pres2[s2[end] + 1]))\n",
    "        return ans % mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mapping = {}\n",
    "        for i, v in enumerate(nums1):\n",
    "            mapping[v] = [i, -1]\n",
    "        for i, v in enumerate(nums2):\n",
    "            if v in mapping:\n",
    "                mapping[v][1] = i\n",
    "            else:\n",
    "                mapping[v] = [-1, i]\n",
    "        \n",
    "        i, j = 0, 0\n",
    "        s1, s2 = 0, 0\n",
    "\n",
    "        while i < len(nums1) and j < len(nums2):\n",
    "            if nums1[i] < nums2[j]:\n",
    "                s1 += nums1[i]\n",
    "                i += 1\n",
    "            elif nums1[i] > nums2[j]:\n",
    "                s2 += nums2[j]\n",
    "                j += 1\n",
    "            else:\n",
    "                s1 = s2 = max(s1, s2)+nums1[i]\n",
    "                i += 1\n",
    "                j += 1\n",
    "        if i < len(nums1):\n",
    "            s1 += sum(nums1[i:])\n",
    "        if j < len(nums2):\n",
    "            s2 += sum(nums2[j:])\n",
    "        return max(s1, s2)%(pow(10,9)+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        nums = list(set(nums1 + nums2))\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        nums_dict = {num: i for i, num in enumerate(nums)}\n",
    "        nums1_dict = {num: i for i, num in enumerate(nums1)}\n",
    "        nums2_dict = {num: i for i, num in enumerate(nums2)}\n",
    "\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[nums_dict[nums1[0]]] = nums1[0]\n",
    "        dp[nums_dict[nums2[0]]] = nums2[0]\n",
    "        for i, num in enumerate(nums[1:], 1):\n",
    "            if num in nums1_dict:\n",
    "                j = nums1_dict[num]\n",
    "                if j: \n",
    "                    j = nums_dict[nums1[j - 1]]\n",
    "                    dp[i] = max(dp[i], dp[j] + num)\n",
    "            if num in nums2_dict:\n",
    "                j = nums2_dict[num]\n",
    "                if j: \n",
    "                    j = nums_dict[nums2[j - 1]]\n",
    "                    dp[i] = max(dp[i], dp[j] + num)\n",
    "        # print(dp, nums)\n",
    "        return max(dp[nums_dict[nums1[-1]]], dp[nums_dict[nums2[-1]]]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        s1 = set(nums1)\n",
    "        s2 = set(nums2)\n",
    "        dic1 = {}\n",
    "        dic2 = {}\n",
    "\n",
    "        n1 = len(nums1)\n",
    "        n2 = len(nums2)\n",
    "        for i in range(n1):\n",
    "            dic1[nums1[i]] = i\n",
    "        for i in range(n2):\n",
    "            dic2[nums2[i]]=i\n",
    "        dp1 = [0] * n1\n",
    "        dp2 = [0] * n2\n",
    "        lst = sorted(list(s1 | s2), reverse=True)\n",
    "        ans = {}\n",
    "        for i in range(len(lst)):\n",
    "            cur = lst[i]\n",
    "            ans1 = 0\n",
    "            if cur in dic1:\n",
    "                if dic1[cur] == n1-1:\n",
    "                    ans1 = cur\n",
    "                else:\n",
    "                    ans1 = cur + ans[nums1[dic1[cur] + 1]]\n",
    "            if cur in dic2:\n",
    "                if dic2[cur] == n2-1:\n",
    "                    ans1 = max(ans1, cur)\n",
    "                else:\n",
    "                    ans1 = max(ans1, cur + ans[nums2[dic2[cur] + 1]])\n",
    "            ans[lst[i]] = ans1\n",
    "        return max(ans[nums1[0]],ans[nums2[0]])%(10**9+7)\n",
    "            \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
